package OptimalManyServices;


import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

public class test {
    public static void main(String[] args) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader("src\\OptimalManyServices\\test\\waits1.in"));

            BufferedWriter writer = new BufferedWriter(new FileWriter("./output.txt"));

//从文件中读出信息

            String info = reader.readLine();

            String[] infos = info.split(" ");

            int n = Integer.parseInt(infos[0]);// 顾客数

            int s = Integer.parseInt(infos[1]);// 提供的服务数

//System.out.println(n + " " + s);

            info = reader.readLine();

//System.out.println(info);

            infos = info.split(" ");

            int[] time = new int[n]; // 每个顾客需要的服务时间

            for (int i = 0; i < infos.length; i++) {
                time[i] = Integer.parseInt(infos[i]);

            }

// 冒泡排序(按时间进行排序)

            for (int i = 0; i < time.length; i++) {
                int temp = 0;

                for (int j = i + 1; j < time.length; j++) {
                    if (time[i] > time[j]) {
                        temp = time[i];

                        time[i] = time[j];

                        time[j] = temp;

                    }

                }

            }

// 进行排放

            int sum = 0;// 用来存放所有顾客的等待时间

            sum = sum + time[0] + time[1];// 先把第一二个人的时间加在上面

            int[] waitTime = new int[n];

            waitTime[0] = time[0];

            waitTime[1] = time[1];

            for(int i = 2; i < n; i++) {
                if(waitTime[i-2] < waitTime[i-1]){
                    waitTime[i] = waitTime[i-2] + time[i];

                }else {
                    waitTime[i] = waitTime[i-1] + time[i];

                }

                sum = sum + waitTime[i];

            }

// 写入文件中

            int x = sum/n;

// 可以用一下三种方式先把整数转化为string，再进行存储

//writer.write(x + "");

//writer.write(String.valueOf(x));

            writer.write(Integer.toString(x));

            writer.flush();

        } catch (FileNotFoundException e) {
// TODO 自动生成的 catch 块

            e.printStackTrace();

        } catch (IOException e) {
// TODO 自动生成的 catch 块

            e.printStackTrace();

        }

    }

}